1. Field of the Invention
The present invention relates to motion estimation, and more particularly, to a low-power consumption, fast motion estimation circuit and method for full search block matching.
2. Description of the Related Art
For a television receiver or monitor displaying continuous motion by variations in a predetermined number of non-continuous frames, about 30 frames per second are displayed based on the afterimage effect of human eyes. These 30 successive frames are obtained by dividing a full image signal for 1 second. Data compression/decompression is necessary to display such a large amount of moving picture data on a monitor.
Two successive frames are almost the same with small variations due to motion. Accordingly, after dividing each frame into a plurality of blocks, the frame is checked to determine a location to which an arbitrary block of the current frame moves in the next frame. If only the displacement of the block is expressed as data using the original information of the block of the current frame, the amount of data to be processed can be reduced. For two successive frames, most of the constituent blocks have common data although their positions are changed. Therefore, data can be effectively compressed based on this fact.
As described above, numerically expressing the displacement of an arbitrary block of a frame to a position in the next block is referred to as “motion estimation”. In motion estimation, motion information is extracted from a video data sequence. In particular, the previous frame is searched to determine that an arbitrary block (reference block) of the current frame originates from which block (candidate block) of the previous frame. Here, the range of searching for a block in the previous frame, which has the same data as the reference block, is limited. This limited range of searching is referred to as a “search range” or “search window”.
Motion vector is a function that defines the position of a candidate block in the previous frame, which is most similar to the reference block. A variety of techniques are available to calculate motion vector. A typical technique is to use the full search block matching algorithm which is most suitable for motion estimation in H.26X and MPEG-1/2/4 video encoding. However, the full search block matching algorithm needs a number of computations and thus increases the processing time.
FIG. 1 shows a search window [−p, p]. Referring to FIG. 1, among candidate blocks in an arbitrary search window for block matching with a reference block, when a candidate block displaced from the reference block by i (i is an integer) along the X-axis and by j (j is an integer) along the Y-axis, i.e., best matches with the reference block, which has a minimum accumulated absolute difference (AAD) value. The reference block has a motion vector of (i, j) with respect to the previous frame. If the search window ranges in [−p, p], the number of candidate blocks for the reference block is equal to (2p+1)2 in the search window. The function to calculate the AAD value is given by formula (1):                                           AAD            ⁡                          (                              m                ,                n                            )                                =                                    ∑                              i                =                0                                            N                -                1                                      ⁢                                                  ⁢                                          ∑                                  j                  =                  0                                                  M                  -                  1                                            ⁢                                                          ⁢                                                                                    X                                          i                      ,                      j                                                        -                                      Y                                                                  (                                                  i                          +                          m                                                )                                            ,                                              (                                                  j                          +                          n                                                )                                                                                                                                                ,        m        ,                  n          ∈                      [                                          -                p                            ,              p                        ]                                              (        1        )            
Motion vector can be expressed as follows using the AAD function of formula (1) above:mv(m,n)=min AAD(m,n)  (2)
In formula (1) above, X denotes a macro block (i.e., reference block) of the reference frame, and Y denotes a macro block (i.e., candidate block) of the previous frame. To search for the most similar candidate block to the reference block of the reference frame, an accumulated absolute difference between data of a plurality of pixels composing the reference block and data of a plurality of pixels comprising each candidate block in the search window is calculated, and a candidate block having a minimum accumulated absolute difference is selected as the most similar candidate block by using the motion vector.
In general, an SIF image consists of 330 (=22×15) macro blocks each of which includes 16×16 (=N×M) pixels. Supposing that the search window for each macro block is [−p, p], a total of (2p+1)2 AADs is required to calculate the motion vector of each macro block. Each AAD value is calculated by accumulating absolute difference values between the reference block pixel data and the corresponding candidate block pixel data, wherein each block has N×M pixel values. The position of a candidate block in the search window, which has the minimum AAD among the resulting AADs, is defined as a motion vector.
To calculate the motion vector of one macro block, a number of computations are needed, as described by formula (1) above. Therefore, to provide a compressed video image in real time, considerable processor elements (PEs) are required for parallel processing.